//
//  Problem1025.swift
//  TestProject
//
//  Created by 武侠 on 2021/2/19.
//  Copyright © 2021 zhulong. All rights reserved.
//

/*
 1025. 除数博弈
 爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。

 最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：

 选出任一 x，满足 0 < x < N 且 N % x == 0 。
 用 N - x 替换黑板上的数字 N 。
 如果玩家无法执行这些操作，就会输掉游戏。

 只有在爱丽丝在游戏中取得胜利时才返回 True，否则返回 False。假设两个玩家都以最佳状态参与游戏。

 示例 1：
     输入：2
     输出：true
     解释：爱丽丝选择 1，鲍勃无法进行操作。

 示例 2：
     输入：3
     输出：false
     解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。  

 提示：

 1 <= N <= 1000
 */
import UIKit

@objcMembers class Problem1025: NSObject {
    func solution() {
        for i in 1...12 {
            print(i, divisorGameFunc1(i))
        }
    }

    /*
     动态规划
     1: 创建一个数组 dp[N]
     2: dp[i]: N = i时，爱丽丝能够赢 存储1，输 存储0
     3: dp[i] = [1...i) 找到所有 能够N%i==0的值，然后 == !dp[N-i], 只要dp[N-1] == 0 那么dp[N] == 1, 就返回
     */
    func divisorGame(_ N: Int) -> Bool {
        if N == 1 {
            return false
        } else if N == 2 {
            return true
        }
        var dp = Array(repeating: -1, count: N + 1)
        dp[1] = 0
        dp[2] = 1
        
        let result = divisorGameDeep(N, &dp)
        print(dp, result)
        return result == 0 ? false : true
    }
    
    // 递归的方法
    func divisorGameDeep(_ N: Int, _ dp: inout[Int]) -> Int {
        if dp[N] != -1 {
            return dp[N]
        }
        for i in 1..<N {
            if N % i == 0 {
                dp[N-i] = divisorGameDeep(N-i, &dp)
//                print(i, N-i, dp[N-i])
                if dp[N-i] == 0 {
                    dp[N] = 1
                    return 1
                }
            }
        }
        dp[N] = 0
        return 0
    }
    
    // 使用一个函数的方法
    func divisorGameFunc1(_ N: Int) -> Bool {
        if N == 1 {
            return false
        } else if N == 2 {
            return true
        }
        var dp = Array(repeating: false, count: N + 1)
        dp[1] = false
        dp[2] = true
        
        for i in 3...N {
            for j in 1..<i {
                if i % j == 0 && dp[i - j] == false {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[N]
    }
}
